//The DNA sequence is composed of a series of nucleotides abbreviated as 'A', 'C
//', 'G', and 'T'. 
//
// 
// For example, "ACGAATTCCG" is a DNA sequence. 
// 
//
// When studying DNA, it is useful to identify repeated sequences within the DNA
//. 
//
// Given a string s that represents a DNA sequence, return all the 10-letter-lon
//g sequences (substrings) that occur more than once in a DNA molecule. You may re
//turn the answer in any order. 
//
// 
// Example 1: 
// Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
//Output: ["AAAAACCCCC","CCCCCAAAAA"]
// Example 2: 
// Input: s = "AAAAAAAAAAAAA"
//Output: ["AAAAAAAAAA"]
// 
// 
// Constraints: 
//
// 
// 1 <= s.length <= 105 
// s[i] is either 'A', 'C', 'G', or 'T'. 
// 
// Related Topics 位运算 哈希表 字符串 滑动窗口 哈希函数 滚动哈希 
// 👍 175 👎 0


package leetcode.editor.cn;

import java.util.*;

//Java：Repeated DNA Sequences
 class P187RepeatedDnaSequences {
    public static void main(String[] args) {
        Solution solution = new P187RepeatedDnaSequences().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<String> findRepeatedDnaSequencesF(String s) {
            HashSet<String> map = new HashSet<>();
            HashSet<String> result = new HashSet<>();
            int len = 10;
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (sb.length() < 10) {
                    sb.append(c);
                }
                if (sb.length() >= 10) {
                    String string = sb.toString();
                    if (map.contains(string)) {
                        result.add(string);
                    } else {
                        map.add(string);
                    }
                    sb.delete(0, 1);
                }
            }
            return new ArrayList<>(result);
        }
        public List<String> findRepeatedDnaSequences(String s) {
            int L = 10, n = s.length();
            if (n <= L) {
                return new ArrayList();
            }

            // rolling hash parameters: base a
            int a = 4, aL = (int)Math.pow(a, L);

            // convert string to array of integers
            Map<Character, Integer> toInt = new
                    HashMap() {{put('A', 0); put('C', 1); put('G', 2); put('T', 3); }};
            int[] nums = new int[n];
            for(int i = 0; i < n; ++i) {
                nums[i] = toInt.get(s.charAt(i));
            }

            int h = 0;
            Set<Integer> seen = new HashSet();
            Set<String> output = new HashSet();
            // iterate over all sequences of length L
            for (int start = 0; start < n - L + 1; ++start) {
                // compute hash of the current sequence in O(1) time
                if (start != 0) {
                    h = h * a - nums[start - 1] * aL + nums[start + L - 1];
                }
                    // compute hash of the first sequence in O(L) time
                else {
                    for(int i = 0; i < L; ++i) {
                        h = h * a + nums[i];
                    }
                }
                // update output and hashset of seen sequences
                if (seen.contains(h)) {
                    output.add(s.substring(start, start + L));
                }
                seen.add(h);
            }
            return new ArrayList<String>(output);
        }
        public List<String> findRepeatedDnaSequencesL(String s) {
            int L = 10, n = s.length();
            if (n <= L) return new ArrayList();

            // rolling hash parameters: base a
            int a = 4, aL = (int)Math.pow(a, L);

            // convert string to array of integers
            Map<Character, Integer> toInt = new
                    HashMap() {{put('A', 0); put('C', 1); put('G', 2); put('T', 3); }};
            int[] nums = new int[n];
            for(int i = 0; i < n; ++i) nums[i] = toInt.get(s.charAt(i));

            int bitmask = 0;
            Set<Integer> seen = new HashSet();
            Set<String> output = new HashSet();
            // iterate over all sequences of length L
            for (int start = 0; start < n - L + 1; ++start) {
                // compute bitmask of the current sequence in O(1) time
                if (start != 0) {
                    // left shift to free the last 2 bit
                    bitmask <<= 2;
                    // add a new 2-bits number in the last two bits
                    bitmask |= nums[start + L - 1];
                    // unset first two bits: 2L-bit and (2L + 1)-bit
                    bitmask &= ~(3 << 2 * L);
                }
                // compute hash of the first sequence in O(L) time
                else {
                    for(int i = 0; i < L; ++i) {
                        bitmask <<= 2;
                        bitmask |= nums[i];
                    }
                }
                // update output and hashset of seen sequences
                if (seen.contains(bitmask)) output.add(s.substring(start, start + L));
                seen.add(bitmask);
            }
            return new ArrayList<String>(output);
        }
    }

//leetcode submit region end(Prohibit modification and deletion)

}